#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
#include <chrono>
#include <cmath>
#include <omp.h>

using namespace std;
// #define UN_PRINT
// #define TEST

#define A_NODE 1
#define B_NODE 0
#define SINGLE_VM 0
#define DOUBLE_VM 1
#define ADD_REQUEST true
#define DEL_REQUEST false

typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<float, float> PFI;
const int VMS_NUM = 110010;
const int SERVER_TYPE_NUM = 110;     //最大服务器型号种类
const int VM_TYPE_NUM = 1010;        //最大虚拟机种类
const int REQUEST_NUM = 200010;       //最大操作数
const int SERVERS_NUM = 20010;       //最大服务器数
const int MAX_INT = 0x3f3f3f3f;        //比较大的数字
const int MAX_DAY = 1010;      //最大天数
const int MAX_VMS_IN_SERVERS = 1010;

int type_servers_cnt = 0, type_vms_cnt = 0;
int cur_servers_cnt = 0, cur_vms_cnt = 0;
int max_server_core = 0, max_server_mem;
int total_day = 0, topK_day = 0, cur_day = 0;
int request_cnt = 0, request_day_cnt[MAX_DAY];
int pre_servers_cnt = 0;
int balance_cnt = 0, total_cnt = 0;
int add_temp1 = 0, add_temp2 = 0, add_temp3 = 0, add_temp4 = 0, add_temp5 = 0, add_temp6 = 0;




//用于线性回归
float a_core, b_mem;  //返回的性价比参数
#ifndef _POINT_H
#define _POINT_H

class Point {
public:
    Point(float x = 0, float y = 0) :x(x), y(y) {}
    float GetX() const { return x; }
    float GetY() const { return y; }
private:
    float x, y;
};
#endif



//直线线性拟合，points 为各点，nPoint 为点数
PFI lineFit(const Point points[], int nPoint) //友元函数体
{
    float avgX = 0, avgY = 0;    //定义变量
    float lxx = 0, lyy = 0, lxy = 0;
    for (int i = 0; i<nPoint; i++)   //计算X、Y的平均值
    {
        avgX += points[i].GetX() / nPoint;
        avgY += points[i].GetY() / nPoint;
    }
    for (int i = 0; i<nPoint; i++)   //计算Lxx、Lyy和Lxy
    {
        lxx += (points[i].GetX() - avgX)*(points[i].GetX() - avgX);
        //        lyy+=(points[i].GetY()-avgY)*(points[i].GetY()-avgY);
        lxy += (points[i].GetX() - avgX)*(points[i].GetY() - avgY);
    }
    //    cout<<"This line can be fitted by y=ax+b."<<endl;
    //    cout<<"a="<<lxy/lxx;  //输出回归系数a
    //    cout<<" b="<<avgY-lxy*avgX/lxx<<endl;   //输出回归系数b
    return { lxy / lxx, avgY - lxy*avgX / lxx }; //返回相关系数r
}

#ifdef TEST
ui total_sum = 0, migration_cnt = 0, server_sum = 0;
#endif

int origin_requests[REQUEST_NUM];
unordered_map<string, int> vm_type_index;    //虚拟机型号->虚拟机型号索引
unordered_map<ull, int> vm_id_index;         //虚拟机id->当前虚拟机索引
int buy_server_list[SERVERS_NUM];                   //购买的列表
vector<deque<int>> new_servers(SERVERS_NUM);       //添加的服务器，
vector<unordered_set<int>> vms_in_servers(SERVERS_NUM);
PII recover_servers_list[MAX_VMS_IN_SERVERS];


struct server {
    string name;
    int core = 0, mem = 0, price = 0, cost = 0;
    double score = -9;
    bool operator<(const server &s) const {
        ui v_1 = price + cost * total_day / 2;
        ui v_2 = s.price + s.cost * total_day / 2;
        return v_1 < v_2;
    }
}type_servers[SERVER_TYPE_NUM];      //服务器结构

struct vm {
    ui core, mem, state;
}type_vm[VM_TYPE_NUM];               //虚拟机结构

struct balance_servers_property {
    ui index, core, mem;
    double availability = 0;
    bool operator<(const balance_servers_property &s) const {
        return availability < s.availability;
    }
};

struct migration_property {
    ui index, vm_cnt, resource;
    ui total_source;
    bool operator<(const migration_property &s) const {
        if (vm_cnt == s.vm_cnt) return resource < s.resource;   //>
        return vm_cnt - total_source / 200.0 < s.vm_cnt - s.total_source / 200.0;//vm_cnt - total_source/200.0 < s.vm_cnt - s.total_source/200.0   vm_cnt  < s.vm_cnt;
    }
};

struct request {
    bool state = true;                  //state = true表示添加
    string name;
    ull id = 0;
    int origin_index;
    bool operator<(const request &s) const {
        ui index = vm_type_index[name], s_index = vm_type_index[s.name];
        ui state_1 = type_vm[index].state == 0 ? 3 : 2, state_2 = type_vm[s_index].state == 0 ? 3 : 2;

        ui r = (type_vm[index].core + type_vm[index].mem) * (state_1)-abs((int)(type_vm[index].core - type_vm[index].mem));
        ui s_r = (type_vm[s_index].core + type_vm[s_index].mem) * (state_2)-abs((int)(type_vm[s_index].core - type_vm[s_index].mem));
        return r > s_r;
    }
}requests[REQUEST_NUM];          //每日操作结构

struct cur_server {
    int type, core_1, core_2, mem_1, mem_2, cost, add_index;
    int cnt_1 = 0, cnt_2 = 0, cnt_3 = 0;
    int total_type = 0;  //表示这个型号服务器总的core和mem之和
    double availability = 0;  //表示当前服务器利用率，0为无，1为满
    double get_availability(){
        availability =  1 - (core_1 + core_2 + mem_1 + mem_2) * 1.0 / total_type;
        return availability;
    }
}cur_servers[SERVERS_NUM];      //当前服务器结构

struct cur_vm {
    ull id;
    int server_index, core, mem, state, node;               //state 0 单核 state 1双核 node true A节点, false B节点
}cur_vms[VMS_NUM];


bool cmp(const cur_server &s_1, const cur_server &s_2) {
    return  s_1.type < s_2.type;
}

bool cmp2(const int &a, const int &b) {
    int state_1 = cur_vms[a].state == 0 ? 1 : 9, state_2 = cur_vms[b].state == 0 ? 1 : 9;
    int r_1 = (cur_vms[a].core + cur_vms[a].mem) * state_1, r_2 = (cur_vms[b].core + cur_vms[b].mem) * state_2;
    return r_1 < r_2;
}

struct find_result {
    int server_index = -1, node;
    int factor = MAX_INT;
};

void load_type() {
    scanf("%d", &type_servers_cnt);      //读服务器型号
    for (int i = 0; i < type_servers_cnt; i++) {
        string _name, _core, _mem, _price, _cost;
        cin >> _name >> _core >> _mem >> _price >> _cost;
        string name;
        int core = 0, mem = 0, price = 0, cost = 0;
        for (int j = 1; j < _name.size() - 1; j++) name += _name[j];
        for (int j = 0; j < _core.size() - 1; j++) core = core * 10 + _core[j] - 48;
        for (int j = 0; j < _mem.size() - 1; j++) mem = mem * 10 + _mem[j] - 48;
        for (int j = 0; j < _price.size() - 1; j++) price = price * 10 + _price[j] - 48;
        for (int j = 0; j < _cost.size() - 1; j++) cost = cost * 10 + _cost[j] - 48;
        type_servers[i].name = name;
        type_servers[i].core = core;
        type_servers[i].mem = mem;
        type_servers[i].price = price;
        type_servers[i].cost = cost;
        max_server_core = max(max_server_core, core);
        max_server_mem = max(max_server_mem, mem);
    }

    scanf("%d", &type_vms_cnt);      //读虚拟机型号
    for (int i = 0; i < type_vms_cnt; i++) {
        string _name, _core, _mem, _state;
        cin >> _name >> _core >> _mem >> _state;
        string name;
        int core = 0, mem = 0, state = 0;
        for (int j = 1; j < _name.size() - 1; j++) name += _name[j];
        for (int j = 0; j < _core.size() - 1; j++) core = core * 10 + _core[j] - 48;
        for (int j = 0; j < _mem.size() - 1; j++) mem = mem * 10 + _mem[j] - 48;
        for (int j = 0; j < _state.size() - 1; j++) state = state * 10 + _state[j] - 48;
        type_vm[i].core = core;
        type_vm[i].mem = mem;
        type_vm[i].state = state;
        vm_type_index[name] = i;
    }
    scanf("%d %d", &total_day, &topK_day);   //输入天数
    sort(type_servers, type_servers + type_servers_cnt);
}

void load_single_day_request(int day) {
    int cur_request_cnt = 0;
    scanf("%d", &cur_request_cnt);
    request_day_cnt[day + 1] = request_day_cnt[day] + cur_request_cnt;
    string _op, _type, _id;
    int start = 0;
    for (int i = 0; i < cur_request_cnt; i++) {
        cin >> _op;
        requests[request_cnt].origin_index = request_day_cnt[day] + i;
        if (_op[1] == 'a') {                      //添加请求
            cin >> _type >> _id;
            string name;
            ull id = 0;
            for (int j = 0; j < _type.size() - 1; j++)  name += _type[j];
            for (int j = 0; j < _id.size() - 1; j++) id = id * 10 + _id[j] - 48;
            requests[request_cnt].name = name;
            requests[request_cnt].id = id;
            requests[request_cnt++].state = ADD_REQUEST;
        }
        else {      //删除请求
            cin >> _id;
            ull id = 0;
            for (int j = 0; j < _id.size() - 1; j++) id = id * 10 + _id[j] - 48;
            requests[request_cnt].id = id;
            requests[request_cnt++].state = false;
            if (start != i) sort(requests + request_day_cnt[day] + start, requests + request_day_cnt[day] + i);
            start = i + 1;
        }
    }
    if (requests[request_cnt - 1].state == ADD_REQUEST) {
        sort(requests + request_day_cnt[day] + start, requests + request_day_cnt[day] + cur_request_cnt);
    }
    for (int i = 0; i < cur_request_cnt; i++) {
        ui cur_index = request_day_cnt[day] + i;
        ui o_index = requests[cur_index].origin_index;
        origin_requests[o_index] = cur_index;
    }
}

void purchase() {    //购买
    int t = 0;
    for (int i = 0; i < type_servers_cnt; i++) {
        if (buy_server_list[i] > 0) t++;
    }
    cout << "(purchase, " + to_string(t) + ")" << endl;
    for (int i = 0; i < type_servers_cnt; i++) {
        if (buy_server_list[i] > 0) cout << "(" + type_servers[i].name + "," + to_string(buy_server_list[i]) + ")" << endl;
    }

}

void display() {
    //虚拟机放置信息
    for (int i = request_day_cnt[cur_day]; i < request_day_cnt[cur_day + 1]; i++) {
        ui cur_index = origin_requests[i];

        string add_res;
        if (requests[cur_index].state == DEL_REQUEST) continue;
        ui vm_index = vm_id_index[requests[cur_index].id];
        if (cur_vms[vm_index].state == SINGLE_VM) {
            add_res += "(" + to_string(cur_vms[vm_index].server_index) + ", ";
            if (cur_vms[vm_index].node == 1) add_res += "A)";
            else add_res += "B)";
        }
        else {
            add_res += "(" + to_string(cur_vms[vm_index].server_index) + ")";
        }
        cout << add_res << endl;
    }
}

void arrange() {
    sort(cur_servers + pre_servers_cnt, cur_servers + cur_servers_cnt, cmp);
    for (int i = pre_servers_cnt; i < cur_servers_cnt; i++) {
        int add_servers_index = cur_servers[i].add_index;
        while (!new_servers[add_servers_index].empty()) {
            ui x = new_servers[add_servers_index].back();
            cur_vms[x].server_index = i;
            vms_in_servers[i].insert(x);
            new_servers[add_servers_index].pop_back();
        }
    }
}

void add_vms(int server_index, int vm_index, int vm_core, int vm_mem, int node, int state, ull vm_id) {
    if (state == SINGLE_VM) {
        if (node == A_NODE) {
            cur_servers[server_index].core_1 -= vm_core;
            cur_servers[server_index].mem_1 -= vm_mem;
            cur_servers[server_index].cnt_1++;
            cur_vms[vm_index].node = A_NODE;
        }
        else {
            cur_servers[server_index].core_2 -= vm_core;
            cur_servers[server_index].mem_2 -= vm_mem;
            cur_servers[server_index].cnt_2++;
            cur_vms[vm_index].node = B_NODE;
        }
        cur_vms[vm_index].state = SINGLE_VM;
        cur_vms[vm_index].mem = vm_mem;
        cur_vms[vm_index].core = vm_core;

    }
    else {
        cur_servers[server_index].core_1 -= vm_core;
        cur_servers[server_index].mem_1 -= vm_mem;
        cur_servers[server_index].core_2 -= vm_core;
        cur_servers[server_index].mem_2 -= vm_mem;
        cur_servers[server_index].cnt_3++;
        cur_vms[vm_index].state = DOUBLE_VM;
        cur_vms[vm_index].mem = vm_mem * 2;
        cur_vms[vm_index].core = vm_core * 2;
    }
    cur_vms[vm_index].server_index = server_index;
    cur_vms[vm_index].id = vm_id;
}



void add_servers(int vm_core, int vm_mem) {
    // 用于存储备选服务器
    int tempi;
    int temp_flag = 0;
    int flag_cnt = 9;
    int temp_mem = 0, temp_core = 0;
    double max_score = -1, temp_score = -1;
    ui p_core = vm_core, p_mem = vm_mem;
    //ph
    double x = 1.3;
    vm_core = min((double)max_server_core / 2, vm_core * x);
    vm_mem = min((double)max_server_mem / 2, vm_mem *x);
    for (int i = 0; i < type_servers_cnt; i++) {
        if ((type_servers[i].core / 2 >= p_core && type_servers[i].mem / 2 >= p_mem && (type_servers[i].mem / 2 + type_servers[i].core / 2) <= p_core + p_mem + 2)
            || (type_servers[i].core / 2 >= vm_core && type_servers[i].mem / 2 >= vm_mem)) {
            temp_score = type_servers[i].score;
            if (temp_flag < flag_cnt) {
                temp_flag++;
                if (temp_score > max_score) {
                    max_score = temp_score;
                    tempi = i;
                }
            }
            else {
                i = tempi;
                temp_mem = type_servers[i].mem;
                temp_core = type_servers[i].core;
                cur_servers[cur_servers_cnt].mem_1 = temp_mem  / 2;
                cur_servers[cur_servers_cnt].mem_2 = temp_mem  / 2;
                cur_servers[cur_servers_cnt].core_1 = temp_core / 2;
                cur_servers[cur_servers_cnt].core_2 = temp_core / 2;
                cur_servers[cur_servers_cnt].type = i;
                cur_servers[cur_servers_cnt].cost = type_servers[i].cost;
                cur_servers[cur_servers_cnt].add_index = cur_servers_cnt - pre_servers_cnt;
                cur_servers[cur_servers_cnt].total_type = temp_core + temp_mem;
                cur_servers_cnt++;
#ifdef TEST
                server_sum += type_servers[i].price;
                total_sum += type_servers[i].price;
#endif
                buy_server_list[i]++;
                return;
            }
        }
    }
    if (temp_flag > 0) {
        int i = tempi;
        if (type_servers[i].core / 2 >= vm_core && type_servers[i].mem / 2 >= vm_mem) {
            temp_mem = type_servers[i].mem;
            temp_core = type_servers[i].core;
            cur_servers[cur_servers_cnt].mem_1 = temp_mem  / 2;
            cur_servers[cur_servers_cnt].mem_2 = temp_mem  / 2;
            cur_servers[cur_servers_cnt].core_1 = temp_core / 2;
            cur_servers[cur_servers_cnt].core_2 = temp_core / 2;
            cur_servers[cur_servers_cnt].type = i;
            cur_servers[cur_servers_cnt].cost = type_servers[i].cost;
            cur_servers[cur_servers_cnt].add_index = cur_servers_cnt - pre_servers_cnt;
            cur_servers[cur_servers_cnt].total_type = temp_core + temp_mem;
            cur_servers_cnt++;
#ifdef TEST
            server_sum += type_servers[i].price;
            total_sum += type_servers[i].price;
#endif
            buy_server_list[i]++;
            return;
        }
    }
}

find_result get_single_factor(int vm_core, int vm_mem, int server_index, bool flag = true, int cur_cnt = 0, double availability = -1) {
    find_result res;
    int n = cur_servers[server_index].cnt_1 + cur_servers[server_index].cnt_2 + cur_servers[server_index].cnt_3;
    if (cur_cnt != 0 && cur_cnt > n) return res;
    if (!flag && n == 0) return res;
    if (cur_servers[server_index].availability <= availability) return res;
    if (cur_servers[server_index].core_1 >= vm_core && cur_servers[server_index].mem_1 >= vm_mem) {
        int cur_factor = (cur_servers[server_index].core_1 + cur_servers[server_index].mem_1 - vm_core - vm_mem);
        ui cur_factor1 = cur_servers[server_index].core_1 - vm_core + 10;
        ui cur_factor2 = cur_servers[server_index].mem_1 - vm_mem + 10;
        int a = max(cur_factor1, cur_factor2), b = min(cur_factor1, cur_factor2);
        cur_factor *= (int)(a * 1.0 / b);
        if (n == 0) cur_factor *= 3;
        res.server_index = server_index;
        res.node = A_NODE;
        res.factor = cur_factor;
    }
    if (cur_servers[server_index].core_2 >= vm_core && cur_servers[server_index].mem_2 >= vm_mem) {
        int cur_factor = (cur_servers[server_index].core_2 + cur_servers[server_index].mem_2 - vm_core - vm_mem);
        int cur_factor1 = cur_servers[server_index].core_2 - vm_core + 10;
        int cur_factor2 = cur_servers[server_index].mem_2 - vm_mem + 10;
        int a = max(cur_factor1, cur_factor2), b = min(cur_factor1, cur_factor2);
        cur_factor *= (int)(a * 1.0 / b);
        if (n == 0) cur_factor *= 3;
        if (cur_factor < res.factor) {
            res.server_index = server_index;
            res.node = B_NODE;
            res.factor = cur_factor;
        }
    }
    return res;
}

PII find_vms_single(int vm_core, int vm_mem, bool flag = true, int cur_cnt = 0, double availability = -1) {
    find_result res[2];
#pragma omp parallel for num_threads(2)
    for (int i = 0; i < cur_servers_cnt; i++) {
        int cur_thread = omp_get_thread_num();
        find_result cur_res = get_single_factor(vm_core, vm_mem, i, flag, cur_cnt, availability);
        if (cur_res.server_index == -1) continue;
        if (cur_res.factor < res[cur_thread].factor) {
            res[cur_thread].factor = cur_res.factor;
            res[cur_thread].server_index = cur_res.server_index;
            res[cur_thread].node = cur_res.node;
        }
    }
    if (res[0].factor < res[1].factor)
        return { res[0].server_index, res[0].node };
    else
        return { res[1].server_index, res[1].node };
}

find_result get_double_factor(int vm_core, int vm_mem, int server_index, bool flag = true, int cur_cnt = 0, double availability = -1) {
    find_result res;
    int n = cur_servers[server_index].cnt_1 + cur_servers[server_index].cnt_2 + cur_servers[server_index].cnt_3;
    if (cur_cnt != 0 && cur_cnt > n) return res;
    if (n == 0 && !flag) return res;
    if (cur_servers[server_index].availability <= availability) return res;
    if (cur_servers[server_index].core_1 >= vm_core && cur_servers[server_index].mem_1 >= vm_mem &&
        cur_servers[server_index].core_2 >= vm_core && cur_servers[server_index].mem_2 >= vm_mem) {
        ui cur_factor_1 = (cur_servers[server_index].core_1 + cur_servers[server_index].mem_1 - vm_core - vm_mem);
        ui cur_factor_2 = (cur_servers[server_index].core_2 + cur_servers[server_index].mem_2 - vm_core - vm_mem);
        ui cur_factor = cur_factor_1 + cur_factor_2 + 5;
        ui cur_factor_core_1 = (cur_servers[server_index].core_1 - vm_core) + 10;
        ui cur_factor_core_2 = (cur_servers[server_index].core_2 - vm_core) + 10;
        ui cur_factor_mem_1 = (cur_servers[server_index].mem_1 - vm_mem) + 10;
        ui cur_factor_mem_2 = (cur_servers[server_index].mem_2 - vm_mem) + 10;
        ui a_1 = max(cur_factor_core_1, cur_factor_mem_1), b_1 = min(cur_factor_core_1, cur_factor_mem_1);
        ui a_2 = max(cur_factor_core_2, cur_factor_mem_2), b_2 = min(cur_factor_core_2, cur_factor_mem_2);
        cur_factor *= (int)(a_1 * 1.0 / b_1);
        cur_factor *= (int)(a_2 * 1.0 / b_2);
        if (n == 0) cur_factor *= 3;
        res.server_index = server_index;
        res.factor = cur_factor;
    }
    return res;
}

int find_vms_double(int vm_core, int vm_mem, bool flag = true, ui cur_cnt = 0, double availability = -1) {
    find_result res[2];
#pragma omp parallel for num_threads(2)
    for (int i = 0; i < cur_servers_cnt; i++) {
        int cur_thread = omp_get_thread_num();
        find_result cur_res = get_double_factor(vm_core, vm_mem, i, flag, cur_cnt, availability);
        if (cur_res.server_index == -1) continue;
        if (cur_res.factor < res[cur_thread].factor) {
            res[cur_thread].server_index = cur_res.server_index;
            res[cur_thread].factor = cur_res.factor;
        }
    }
    if (res[0].factor < res[1].factor)
        return res[0].server_index;
    else
        return res[1].server_index;
}

int balanced(vector<string> &migration_res, ui cur_migration_cnt) {
    ui alive_vms_num = vm_id_index.size();          //总虚拟机数
    ui allowed_cnt = (alive_vms_num * 3 / 100 - cur_migration_cnt);
    ui balanced_cnt = 0, pre_balanced_cnt = 0;
    int b_low_cnt = 0; //表示0-0.95利用率服务器的数目
    double availability_divide = 0;
    double temp_availability = 0;
    vector<balance_servers_property> balanced_servers_list(cur_servers_cnt);
    for (int i = 0; i < cur_servers_cnt; i++){
        temp_availability = cur_servers[i].get_availability();
        if(temp_availability > 0 && temp_availability < 0.96){
            balanced_servers_list[b_low_cnt].index = i;
            balanced_servers_list[b_low_cnt].availability = cur_servers[i].get_availability();
            b_low_cnt ++;
        }
    }

    sort(balanced_servers_list.begin(), balanced_servers_list.begin() + b_low_cnt);

    int vms_list[10100], vms_list_len = 0;
    for (int x = 0; x < b_low_cnt && balanced_cnt < allowed_cnt; x++) {
        availability_divide = balanced_servers_list[x].availability;
        int last_vms_list_len = vms_list_len;
        int s_index = balanced_servers_list[x].index;
        for (int v : vms_in_servers[s_index]) {
            vms_list[vms_list_len++] = v;
            pre_balanced_cnt ++;
            if (pre_balanced_cnt == allowed_cnt) {
                vms_list_len = last_vms_list_len;
                break;
            }
        }
        if (pre_balanced_cnt == allowed_cnt) {
            break;
        }
    }


    sort(vms_list, vms_list + vms_list_len, cmp2);

    for (int i = 0; i < vms_list_len; i++) {
        int vm_index = vms_list[i];
        int s_index = cur_vms[vm_index].server_index;
        ui pre_node = cur_vms[vm_index].node;
        if (balanced_cnt == allowed_cnt) break;
        int n = cur_servers[s_index].cnt_1 + cur_servers[s_index].cnt_2 + cur_servers[s_index].cnt_3;
        if (cur_vms[vm_index].state == SINGLE_VM) {
            PII res = find_vms_single(cur_vms[vm_index].core, cur_vms[vm_index].mem, false,0,availability_divide);
            if(res.first < 0){
                continue;
            }
            if (pre_node == A_NODE) {
                cur_servers[s_index].mem_1 += cur_vms[vm_index].mem;
                cur_servers[s_index].core_1 += cur_vms[vm_index].core;
                cur_servers[s_index].cnt_1--;
            }
            else {
                cur_servers[s_index].mem_2 += cur_vms[vm_index].mem;
                cur_servers[s_index].core_2 += cur_vms[vm_index].core;
                cur_servers[s_index].cnt_2--;
            }
            vms_in_servers[s_index].erase(vm_index);
            add_vms(res.first, vm_index, cur_vms[vm_index].core, cur_vms[vm_index].mem, res.second, SINGLE_VM, cur_vms[vm_index].id);
            vms_in_servers[res.first].insert(vm_index);
            char node = res.second ? 'A' : 'B';
            if (res.first != s_index || (res.first == s_index && res.second != pre_node)) {
                migration_res.emplace_back("(" + to_string(cur_vms[vm_index].id) + ", " + to_string(cur_vms[vm_index].server_index) + ", " + node + ")");
                balanced_cnt++;
            }
            else {
                continue;
            }
        }
        else {
            int res = find_vms_double(cur_vms[vm_index].core / 2, cur_vms[vm_index].mem / 2, false,0,availability_divide);
            if(res < 0){
                continue;
            }
            cur_servers[s_index].mem_1 += cur_vms[vm_index].mem / 2;
            cur_servers[s_index].core_1 += cur_vms[vm_index].core / 2;
            cur_servers[s_index].mem_2 += cur_vms[vm_index].mem / 2;
            cur_servers[s_index].core_2 += cur_vms[vm_index].core / 2;
            cur_servers[s_index].cnt_3--;
            vms_in_servers[s_index].erase(vm_index);
            add_vms(res, vm_index, cur_vms[vm_index].core / 2, cur_vms[vm_index].mem / 2, 0, DOUBLE_VM, cur_vms[vm_index].id);
            vms_in_servers[res].insert(vm_index);
            if (res != s_index) {
                migration_res.emplace_back("(" + to_string(cur_vms[vm_index].id) + ", " + to_string(cur_vms[vm_index].server_index) + ")");
                balanced_cnt++;
            }
            else {
                continue;
            }
        }
    }
    return balanced_cnt;
}

int balanced2(vector<string> &migration_res, ui cur_migration_cnt) {
    ui alive_vms_num = vm_id_index.size();          //总虚拟机数
    ui allowed_cnt = (alive_vms_num * 3 / 100 - cur_migration_cnt);
    ui balanced_cnt = 0;
    vector<balance_servers_property> balanced_servers_list(cur_servers_cnt);
    for (int i = 0; i < cur_servers_cnt; i++) {
        balanced_servers_list[i].index = i;
        balanced_servers_list[i].mem = cur_servers[i].mem_1 + cur_servers[i].mem_2;
        balanced_servers_list[i].core = cur_servers[i].core_1 + cur_servers[i].core_2;
    }

    sort(balanced_servers_list.begin(), balanced_servers_list.end());

    for (int x = 0; x < cur_servers_cnt && balanced_cnt < allowed_cnt; x++) {
        int s_index = balanced_servers_list[x].index;
        int vms_list[1010], vms_list_len = 0;
        for (int v : vms_in_servers[s_index]) {
            vms_list[vms_list_len++] = v;
        }
        sort(vms_list, vms_list + vms_list_len, cmp2);
        for (int i = 0; i < vms_list_len; i++) {
            int vm_index = vms_list[i];
            ui pre_node = cur_vms[vm_index].node;
            if (balanced_cnt == allowed_cnt) break;
            int n = cur_servers[s_index].cnt_1 + cur_servers[s_index].cnt_2 + cur_servers[s_index].cnt_3;
            if (n <= 1) break;
            if (cur_vms[vm_index].state == SINGLE_VM) {
                if (pre_node == A_NODE) {
                    cur_servers[s_index].mem_1 += cur_vms[vm_index].mem;
                    cur_servers[s_index].core_1 += cur_vms[vm_index].core;
                    cur_servers[s_index].cnt_1--;

                }
                else {
                    cur_servers[s_index].mem_2 += cur_vms[vm_index].mem;
                    cur_servers[s_index].core_2 += cur_vms[vm_index].core;
                    cur_servers[s_index].cnt_2--;
                }
                vms_in_servers[s_index].erase(vm_index);
                PII res = find_vms_single(cur_vms[vm_index].core, cur_vms[vm_index].mem, false);
                add_vms(res.first, vm_index, cur_vms[vm_index].core, cur_vms[vm_index].mem, res.second, SINGLE_VM, cur_vms[vm_index].id);
                vms_in_servers[res.first].insert(vm_index);
                char node = res.second ? 'A' : 'B';
                if (res.first != s_index || (res.first == s_index && res.second != pre_node)) {
                    migration_res.emplace_back("(" + to_string(cur_vms[vm_index].id) + ", " + to_string(cur_vms[vm_index].server_index) + ", " + node + ")");
                    balanced_cnt++;
                }
                else {
                    break;
                }
            }
            else {
                cur_servers[s_index].mem_1 += cur_vms[vm_index].mem / 2;
                cur_servers[s_index].core_1 += cur_vms[vm_index].core / 2;
                cur_servers[s_index].mem_2 += cur_vms[vm_index].mem / 2;
                cur_servers[s_index].core_2 += cur_vms[vm_index].core / 2;
                vms_in_servers[s_index].erase(vm_index);
                cur_servers[s_index].cnt_3--;
                int res = find_vms_double(cur_vms[vm_index].core / 2, cur_vms[vm_index].mem / 2, false);
                add_vms(res, vm_index, cur_vms[vm_index].core / 2, cur_vms[vm_index].mem / 2, 0, DOUBLE_VM, cur_vms[vm_index].id);
                vms_in_servers[res].insert(vm_index);
                if (res != s_index) {
                    migration_res.emplace_back("(" + to_string(cur_vms[vm_index].id) + ", " + to_string(cur_vms[vm_index].server_index) + ")");
                    balanced_cnt++;
                }
                else {
                    break;
                }
            }
        }
    }
    return balanced_cnt;
#ifdef TEST
    migration_cnt += balanced_cnt;
#endif
}

PII get_add_num() {
    int sum_c = 0, sum_m = 0;
    for (int i = 0; i < type_vms_cnt; i++) {
        sum_c += type_vm[i].core;
        sum_m += type_vm[i].mem;
    }

    PII res = { -1, -1 };
    res.first = sum_c;
    res.second = sum_m;
    return res;
}

void get_parameter() {
    int sum_core = get_add_num().first;
    int sum_mem = get_add_num().second;
    int sum_all = (sum_core + sum_mem) / type_vms_cnt;
    add_temp1 = sum_all / 7;
    add_temp2 = sum_all * 2 / 3 - 2;
    add_temp3 = sum_core / type_vms_cnt / 6;
    add_temp4 = sum_core / type_vms_cnt * 0.7;
    add_temp5 = sum_mem / type_vms_cnt / 6;
    add_temp6 = sum_mem / type_vms_cnt * 0.7;
}


void recover(ui move_cnt, ui m_1, ui m_2, ui c_1, ui c_2, ui s_i) {
    cur_servers[s_i].core_1 = c_1; cur_servers[s_i].core_2 = c_2; cur_servers[s_i].mem_1 = m_1; cur_servers[s_i].mem_2 = m_2;
    if (move_cnt == 0) return;
    for (int i = 0; i < move_cnt; i++) {
        int v = recover_servers_list[i].first;
        int t_s = cur_vms[v].server_index;
        int node = recover_servers_list[i].second;
        if (cur_vms[v].state == SINGLE_VM) {
            if (cur_vms[v].node == A_NODE) {
                cur_servers[t_s].mem_1 += cur_vms[v].mem;
                cur_servers[t_s].core_1 += cur_vms[v].core;
                cur_servers[t_s].cnt_1--;
                vms_in_servers[t_s].erase(v);
            }
            else {
                cur_servers[t_s].mem_2 += cur_vms[v].mem;
                cur_servers[t_s].core_2 += cur_vms[v].core;
                cur_servers[t_s].cnt_2--;
                vms_in_servers[t_s].erase(v);
            }
        }
        else {
            cur_servers[t_s].mem_1 += cur_vms[v].mem / 2;
            cur_servers[t_s].core_1 += cur_vms[v].core / 2;
            cur_servers[t_s].mem_2 += cur_vms[v].mem / 2;
            cur_servers[t_s].core_2 += cur_vms[v].core / 2;
            cur_servers[t_s].cnt_3--;
            vms_in_servers[t_s].erase(v);
        }
        cur_vms[v].server_index = s_i;
        cur_vms[v].node = node;
    }
}

void save_migration(int server_index, vector<string> &migration_res) {
    char node;
    for (ui v : vms_in_servers[server_index]) {
        if (cur_vms[v].state == SINGLE_VM) {
            if (cur_vms[v].node == A_NODE) node = 'A';
            else node = 'B';
            migration_res.push_back("(" + to_string(cur_vms[v].id) + ", " + to_string(cur_vms[v].server_index) + ", " + node + ")");
        }
        else {
            migration_res.push_back("(" + to_string(cur_vms[v].id) + ", " + to_string(cur_vms[v].server_index) + ")");
        }
    }
}

ui migration(vector<string> &migration_res, ui threshold, ui used_cnt) {
    ui alive_vms_num = vm_id_index.size();          //总虚拟机数
    ui allowed_cnt = alive_vms_num * 3 / 100;      //允许迁移数
    ui total_cnt = allowed_cnt;                     //迁移数上限
    if (allowed_cnt == 0) { return 0; }                 //当迁移数用完时跳出迁移策略
    vector<migration_property> s_p(cur_servers_cnt);//初始化迁移结构（排序方式服务器插入的虚拟机数量从小到大，相同时resource指标从大到小）
    int s_p_index = 0; //标注满足threshold限制条件的s_p
    for (int i = 0; i < cur_servers_cnt; i++) {
        ui cnt = cur_servers[i].cnt_1 + cur_servers[i].cnt_2 + cur_servers[i].cnt_3;
        if (cnt <= threshold && cnt > 0){
            ui s_t = cur_servers[i].type;
            s_p[s_p_index].index = i;
            s_p[s_p_index].vm_cnt = cur_servers[i].cnt_1 + cur_servers[i].cnt_2 + cur_servers[i].cnt_3;
            ui remain_resource = cur_servers[i].mem_1 + cur_servers[i].mem_2 + cur_servers[i].core_1 + cur_servers[i].core_2;
            ui total_resource = type_servers[s_t].mem + type_servers[s_t].core;
            s_p[s_p_index].total_source = total_resource;
            s_p[s_p_index].resource = total_resource - remain_resource;
            s_p_index ++;
        }
    }
    sort(s_p.begin(), s_p.begin() + s_p_index);

    for (int x = 0; x < s_p_index && allowed_cnt > 0; x++) {
        int i = s_p[x].index;
        ui move_cnt = 0;
        ui cnt = cur_servers[i].cnt_1 + cur_servers[i].cnt_2 + cur_servers[i].cnt_3;
        if (cnt == 0) continue;
        if (cnt > allowed_cnt) continue;
        if (cnt > threshold) continue;
        ui mem_1 = cur_servers[i].mem_1, mem_2 = cur_servers[i].mem_2, core_1 = cur_servers[i].core_1, core_2 = cur_servers[i].core_2;  //保存服务器信息
        cur_servers[i].mem_1 = 0; cur_servers[i].mem_2 = 0, cur_servers[i].core_1 = 0, cur_servers[i].core_2 = 0;   //暂时禁用服务器

        bool flag = true;
        for (ui v : vms_in_servers[i]) {
            if (cur_vms[v].state == SINGLE_VM) {
                PII res = find_vms_single(cur_vms[v].core, cur_vms[v].mem, false);
                if (res.first == -1) { flag = false; break; }
                recover_servers_list[move_cnt++] = { v, cur_vms[v].node };
                add_vms(res.first, v, cur_vms[v].core, cur_vms[v].mem, res.second, SINGLE_VM, cur_vms[v].id);
                vms_in_servers[res.first].insert(v);
            }
            else {
                int res = find_vms_double(cur_vms[v].core / 2, cur_vms[v].mem / 2, false);
                if (res == -1) { flag = false; break; }
                recover_servers_list[move_cnt++] = { v, cur_vms[v].node };
                add_vms(res, v, cur_vms[v].core / 2, cur_vms[v].mem / 2, B_NODE, DOUBLE_VM, cur_vms[v].id);
                vms_in_servers[res].insert(v);
            }
        }
        if (!flag) {
            recover(move_cnt, mem_1, mem_2, core_1, core_2, i);
            continue;
        }

#ifndef UN_PRINT
        save_migration(i, migration_res);
#endif
        cur_servers[i].cnt_1 = 0;
        cur_servers[i].cnt_2 = 0;
        cur_servers[i].cnt_3 = 0;
        vms_in_servers[i].clear();
        ui type_index = cur_servers[i].type;
        cur_servers[i].mem_1 = type_servers[type_index].mem / 2;
        cur_servers[i].mem_2 = type_servers[type_index].mem / 2;
        cur_servers[i].core_1 = type_servers[type_index].core / 2;
        cur_servers[i].core_2 = type_servers[type_index].core / 2;
        allowed_cnt -= cnt;

#ifdef TEST
        migration_cnt += cnt;
#endif
    }

    return total_cnt - allowed_cnt;
}

void execute_today_request() {
    for (int i = request_day_cnt[cur_day]; i < request_day_cnt[cur_day + 1]; i++) {
        bool op = requests[i].state;            //请求类型
        ull vm_id = requests[i].id;             //请求id
        if (op == ADD_REQUEST) {
            string vm_type = requests[i].name;  //型号
            int vm_t_index = vm_type_index[vm_type]; //型号索引
            int vm_state = type_vm[vm_t_index].state;   //虚拟机放置类型
            int vm_core = type_vm[vm_t_index].core;
            int vm_mem = type_vm[vm_t_index].mem;

            if (vm_state == SINGLE_VM) {
                PII res = find_vms_single(vm_core, vm_mem);
                if (res.first < 0) {
                    add_servers(vm_core, vm_mem);
                    res = find_vms_single(vm_core, vm_mem);
                }
                add_vms(res.first, cur_vms_cnt, vm_core, vm_mem, res.second, SINGLE_VM, vm_id);
                if (res.first < pre_servers_cnt) vms_in_servers[res.first].insert(cur_vms_cnt);
                if (res.first >= pre_servers_cnt)
                    new_servers[res.first - pre_servers_cnt].push_back(cur_vms_cnt);
            }
            else {
                int res = find_vms_double(vm_core / 2, vm_mem / 2);
                if (res < 0) {  //失败
                    add_servers(vm_core / 2, vm_mem / 2);   //添加服务器
                    res = find_vms_double(vm_core / 2, vm_mem / 2);    //再次添加
                }
                add_vms(res, cur_vms_cnt, vm_core / 2, vm_mem / 2, 0, DOUBLE_VM, vm_id);
                if (res < pre_servers_cnt) vms_in_servers[res].insert(cur_vms_cnt);
                if (res >= pre_servers_cnt) new_servers[res - pre_servers_cnt].push_back(cur_vms_cnt);
            }
            vm_id_index[vm_id] = cur_vms_cnt++;     //map记录对应id所在索引
        }
        else {
            int vms_index = vm_id_index[vm_id];  //读取索引
            int server_index = cur_vms[vms_index].server_index;  //读取服务器索引
            int vm_core = cur_vms[vms_index].core;
            int vm_mem = cur_vms[vms_index].mem;
            if (cur_vms[vms_index].state == SINGLE_VM) {
                if (cur_vms[vms_index].node == A_NODE) {
                    cur_servers[server_index].core_1 += vm_core;
                    cur_servers[server_index].mem_1 += vm_mem;
                    cur_servers[server_index].cnt_1--;
                }
                else {
                    cur_servers[server_index].core_2 += vm_core;
                    cur_servers[server_index].mem_2 += vm_mem;
                    cur_servers[server_index].cnt_2--;
                }
            }
            else {
                vm_core /= 2, vm_mem /= 2;
                cur_servers[server_index].core_1 += vm_core;
                cur_servers[server_index].mem_1 += vm_mem;
                cur_servers[server_index].core_2 += vm_core;
                cur_servers[server_index].mem_2 += vm_mem;
                cur_servers[server_index].cnt_3--;
            }
            vms_in_servers[server_index].erase(vms_index);
            vm_id_index.erase(vm_id);       //map删除这台虚拟机
        }
    }
}

// 存储用于线性回归的对应参数
Point p[SERVER_TYPE_NUM];
// 预期服务器运行时间
float cal_day;


//获取性价比参数
double get_score(int id) {
    return (a_core * type_servers[id].core + b_mem * type_servers[id].mem - type_servers[id].price - type_servers[id].cost * cal_day) / (type_servers[id].price + type_servers[id].cost * cal_day);
}

// 返回性价比指标参数
PFI find_cost_performance(int day) {
    float core, mem, price, cost;
    if (total_day == 800) {
        //        if(day < 300)
        //            cal_day = total_day  -day * 1.5;
        //        else
        //            cal_day = (total_day - day)/2;
        cal_day = (total_day - day) * 1.15;
    }
    else {
        //        cal_day = pow((total_day - day) * 1.0/ total_day, 2) * total_day;
        //        cal_day =(1- pow(day * 1.0/ total_day, 2)) * total_day;
        cal_day = total_day - day;
    }
    //    if(total_day == 1000){
    //        cal_day = total_day - day;
    //    }else{
    //        cal_day = (1 - pow(day * 1.0/ total_day, 2)) * total_day;
    //
    //    }
    for (int i = 0; i < type_servers_cnt; i++) {
        core = type_servers[i].core;
        mem = type_servers[i].mem;
        price = type_servers[i].price;
        cost = type_servers[i].cost;
        p[i] = Point(core / mem, (price + cal_day * cost) / mem);
    }
    return lineFit(p, type_servers_cnt);

}



void work() {
    for (int i = 0; i < topK_day; i++)
        load_single_day_request(i);
    for (cur_day = 0; cur_day < total_day; cur_day++) {
        // 获取当天性价比参数
        a_core = find_cost_performance(cur_day).first;
        b_mem = find_cost_performance(cur_day).second;
        // 为每个型号的服务器进行性价比评分
        for (int j = 0; j < type_servers_cnt; j++) {
            type_servers[j].score = get_score(j);
        }
        vector<string> migration_res;                    //保留结果
        int used_cnt = migration(migration_res, 2, 0);
        used_cnt += balanced(migration_res, used_cnt);
        used_cnt += balanced2(migration_res,used_cnt);

        pre_servers_cnt = cur_servers_cnt;
        memset(buy_server_list, 0, sizeof buy_server_list);       //初始化购买服务器列表
        execute_today_request();
        arrange();
#ifndef UN_PRINT
        purchase();
        cout << "(migration, " << migration_res.size() << ")" << endl;
        for (string &x : migration_res) cout << x << endl;
        display();
#endif
        fflush(stdout);
        if (cur_day + topK_day < total_day) load_single_day_request(cur_day + topK_day);
#ifdef TEST
        for (int i = 0; i < cur_servers_cnt; i++) {
            if (cur_servers[i].cnt_1 == 0 && cur_servers[i].cnt_2 == 0 && cur_servers[i].cnt_3 == 0) continue;
            total_sum += cur_servers[i].cost;
        }
        if (cur_day % 100 == 0)
            cout << cur_day << endl;
        total_cnt += used_cnt;
#endif
    }
}

int main() {

#ifdef TEST
    cout << "TEST START" << endl;
    //ph
    string read_path = "D:\\hw_data\\training-1.txt";
    std::freopen(read_path.c_str(), "rb", stdin);
    auto start_time = chrono::steady_clock::now();
    load_type();
    work();

    auto end_time = chrono::steady_clock::now();
    cout << "time :" << chrono::duration<float>(end_time - start_time).count() << endl;
    cout << "total_price :" << total_sum << endl;
    cout << "server_price :" << server_sum << endl;
    cout << "total_cnt :" << total_cnt <<endl;
#endif

#ifndef TEST
    load_type();
    work();
#endif
    return 0;
}
